1. Field of the Invention
The present invention relates to computer graphics generation and display, and more particularly to a method and apparatus for providing the interpolated display characteristic values of pels within a polygon to be displayed.
2. Description of the Background Art
Computer Graphics display systems are computer systems which generate and display graphic images on a raster scan display device. Such graphic images are derived from digital data stored in the system's memory. The data is typically stored in the form of points in a two or three-dimensional coordinate system, wherein the points correspond to the vertices of polygons, such as triangles. The polygons form the "building blocks" of larger objects which are the ultimate display objects. Also stored with the vertex data are parametric values, i.e., intensity, or other values that permit computation of intensity such as surface color, surface reflectivity, transparency, light sources, and normal vectors.
For a given object, this data is stored in the form of a list of instructions, called a "display list". To convert such a display list to an actual image on a raster scan display, a display processor is provided which reads the list from memory, processes the data, and then writes raw pel data to a frame buffer. In raster scan real time the frame buffer is read, and the resulting data stream is converted to an analog video signal which is sent to the display device.
The present invention relates to a function provided in the display processor portion of such computer graphic systems. Specifically, the invention relates to the generation of data relating to a third parametric value for all pel values of a displayed triangle, based on the position of the pels and on other data relating to the third parameter. For example, in the so-called shading problem shading information for a given triangle may be provided to the display processor in the form of the light intensity of the vertices of the triangle. Alternatively, the display processor may be provided the parameters of the object surface, the surface orientation, and the specified light model. The display processor must then, for each pel associated with the triangle, compute a light intensity value based on the values provided.
Prior art approaches to the shading problem generally involve "Gouraud shading" implemented in connection with polygons. For example, in one approach the intensity of points on the polygons are computed in two steps. First, the intensities of all pels associated with each edge are computed as a function of the edge end points (vertices) usng one-dimensional linear interpolation. Then, the intensity of pels in each row (or column) belonging to the polygon is computed as a function of the previously computed intensities, interpolating between two end (edge) points. It will be understood that intensity in this context refers to the brightness of pels, if the object is in grey scale (monochrome) or to R, G, and B values, if the object is in color.
Another example is described in "A 3-D Graphic Display System With Depth Buffer and Pipeline Processor," by A. Fujimoto, et al, IEEE CG & A, (June 1984), page 11. According to the approach described therein, elemental display polygons are first "tesselated", or divided into triangles. This ensures that the triangle being dealt with defines a unique plane. The intensity of each pel is obtained by applying the aforementioned linear interpolation method, the intensity of each pel being obtained from the intensity of previous, contiguous pels by the addition of a fixed, incremental quantity for an X move, and another fixed incremental quantity for a Y move.
A problem with the Fujimoto approach is that the arithmetic precision to represent the increments must be high enough to prevent an excessive accumulation error buildup when the process is repetitively applied to all points of the triangle.
Another example of the function to which the present invention relates is the computation of the Z values of each pel associated with a triangle, based upon the X, Y and Z values of the vertices of the triangle. The prior art approaches to the computation are basically the same as the previously described approach to the computation of the intensity value for each point on a triangle.
The most important disadvantage of these prior art approaches is the lack of accuracy in the computed intensities (or Z values) due to the quantization of the X and Y coordinates or error accumulation. In practical raster scan computer graphics systems, lines defining edges are not always true straight lines. The position of a point on a triangle edge may diverge from its theoretical position and, therefore, the computed intensity may depart from its correct value.
The present invention solves this problem and provides the intensity of each point on the polygon with an error that never exceeds 0.5 intensity units. Additionally, this improvement is provided by way of a method and apparatus that offers increased performance over prior art approaches. Further, the invention has application to the determination of other quantities, such as Z values for pels.